#include<iostream>
#include<assert.h>
using namespace std;

namespace Wang
{
template<class T>
class vector
{
    T* _start = nullptr;
    T* _finish = nullptr;
    T* _end_of_storage = nullptr;
public:
    
    // 强制编译器生成默认构造
    vector() = default;

    // 不能给0，T若为string。T()是匿名对象，调用默认构造。对内置类型，int() = 0，C语言不支持
    vector(size_t n, const T& x = T()) 
    {
        _start = new T[n];
        _finish = _end_of_storage = _start + n;
        for(T* i = _start; i != _finish; i++)
            *i = x;
    }
    vector(int n, int x = 0)
    {
        _start = new T[n];
        _finish = _end_of_storage = _start + n;
        for(T* i = _start; i != _finish; i++)
            *i = x;
    }
    vector(const initializer_list<T>& il)
    {
        reserve(il.size());
        for(auto& e : il)
            push_back(e);
    }
    // 类模板的成员函数，可以有函数模板
    template<class Iterator>
    vector(Iterator first, Iterator last)
    {
        while(first != last)
        {
            push_back(*first);
            ++first;
        }
    }
    
    // vector(const vector& v)
    vector(const vector<T>& v)
    {
        _start = new T[v.size()];
        for(T* i = _start, *j = v._start; j != v._finish; i++, j++)
            *i = *j;
        _finish = _end_of_storage = _start + v.size();
    }

    void swap(vector<T>& t)
    {
        std::swap(_start, t._start);
        std::swap(_finish, t._finish);
        std::swap(_end_of_storage, t._end_of_storage);
    }
    vector<T>& operator= (const vector<T>& v)
    {
        if(this != &v)
        {
            vector<T> tmp(v);
            swap(tmp);
        }
        return *this;
    }

    void Print()
    {
        for(auto& e : *this)
            cout << e << ' ';
        cout << endl;
    }
    ~vector()
    {
        delete[] _start;
        _start = _finish = _end_of_storage = nullptr;
    }

    size_t size() const { return _finish - _start; }
    size_t capacity() const { return _end_of_storage - _start; }
    bool empty() const { return _start == _finish; }
    
    T& operator[](size_t pos)
    {
        assert(pos < size());
        return _start[pos];
    }

    const T& operator[](size_t pos) const
    {
        assert(pos < size());
        return _start[pos];
    }
    void reserve(size_t n)
    {
        if (n > capacity())
        {
            T* new_start = new T[n];
            // memcpy(new_start, _start, sizeof(T) * size());
            
            for (T* i = _start, *j = new_start; i != _finish; i++, j++)
                *j = *i;

            size_t old_size = size();
            delete[] _start;
            _start = new_start;
            _finish = _start + old_size;
            _end_of_storage = _start + n;
        }
    }
    void push_back(const T& x)
    {
        if (_finish == _end_of_storage)
        {
            size_t c = capacity();
            reserve(c == 0 ? 4 : 2 * c);
        }
        *_finish = x;
        _finish++;
    }

    void pop_back()
    {
        assert(_start != _finish);
        --_finish;
    }

    typedef T* iterator;
    typedef const T* const_iterator;

    // insert扩容会使迭代器失效
    iterator insert(iterator pos, const T& x)
    {
        assert(pos >= begin() && pos <= end());
        size_t index = pos - begin();   
        if(_finish == _end_of_storage) reserve(capacity() == 0 ? 4 : 2 * capacity());
        pos = begin() + index;

        for(iterator i = _finish; i != pos; i--)
            *i = *(i-1);
        *pos = x;
        ++_finish;
        return pos;
    }

    // erase迭代器失效, 删除最后一个元（有的编译器可能会缩容）
    iterator erase(iterator pos)
    {
        assert(pos >= begin() && pos < end());
        for(auto i = pos; i != end() - 1; i++)
            *i = *(i + 1);
        --_finish;
        return pos;
    }
    // 迭代器

    iterator begin() { return _start; }
    iterator end() { return _finish; }
    const_iterator begin() const { return _start; }
    const_iterator end() const { return _finish; }
};


} // namespace Wang